//通过两个treemap分别记录所有可出栈的index和所有可入栈的index
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.TreeSet;

public class Solution1172 {

    int capacity;
    List<Stack<Integer>> list=new ArrayList<>();
    TreeSet<Integer> pushSet=new TreeSet<>();
    TreeSet<Integer> popSet=new TreeSet<>((a,b)->b-a);

    public Solution1172(int capacity) {
        this.capacity=capacity;
    }

    public void push(int val) {
        if (pushSet.size()==0){
            Stack<Integer> stack=new Stack<>();
            stack.push(val);
            list.add(stack);
            int index=list.size()-1;
            popSet.add(index);
            if (stack.size()<capacity){
                pushSet.add(index);
            }
        }else {
            int index=pushSet.first();
            Stack<Integer> stack=list.get(index);
            stack.push(val);
            popSet.add(index);
            if (stack.size()==capacity){
                pushSet.remove(index);
            }
        }
    }

    public int pop() {
        if (popSet.size()==0){
            return -1;
        }
        int index=popSet.first();
        Stack<Integer> stack=list.get(index);
        int ans=stack.pop();
        pushSet.add(index);
        if (stack.size()==0){
            popSet.remove(index);
        }
        return ans;
    }

    public int popAtStack(int index) {
        if (list.size()<=index || list.get(index).size()==0){
            return -1;
        }
        Stack<Integer> stack=list.get(index);
        int ans=stack.pop();
        pushSet.add(index);
        if (stack.size()==0){
            popSet.remove(index);
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution1172 solution1172=new Solution1172(2);
        solution1172.push(1);
        solution1172.push(2);
        solution1172.push(3);
        solution1172.push(4);
        solution1172.push(5);
        System.out.println(solution1172.popAtStack(0));
        solution1172.push(20);
        solution1172.push(21);
        System.out.println(solution1172.popAtStack(0));
        System.out.println(solution1172.popAtStack(2));
        System.out.println(solution1172.pop());
        System.out.println(solution1172.pop());
        System.out.println(solution1172.pop());
        System.out.println(solution1172.pop());
        System.out.println(solution1172.pop());
    }
}
